﻿using System.Collections.Generic;
using Algoritmia.Schemes;
using Algoritmia.StateSpaces;

namespace Algoritmia.Problems.RegularExpressions.Greedy
{
    public class RegularExpressionMatchingStateSpace : 
        IForwardStateSpace<RegularExpressionMatchingStateSpace.State,
                           RegularExpressionMatchingStateSpace.State>
    {
        private readonly Dfa _dfa;
        private readonly string _s;

        public RegularExpressionMatchingStateSpace(Dfa dfa, string s)
        {
            _dfa = dfa;
            _s = s;
        }

        public class State
        {
            public int Index { get; private set; }
            public int Q { get; private set; }

            public State(int index, int state)
            {
                Q = state;
                Index = index;
            }
        }

        #region Implementation of IForwardStateSpace<State,State>

        public State Decide(State state, State decision)
        {
            return decision;
        }

        public IEnumerable<State> Decisions(State state)
        {
            if ( state.Index < _s.Length)
            {
                int? destination = _dfa.Destination(state.Q, _s.Substring(state.Index, 1));
                if ( destination.HasValue)
                {
                    yield return new State(state.Index+1,destination.Value);
                    yield break;
                }
            }
            yield return null;
        }

        public IEnumerable<State> InitialStates
        {
            get { yield return new State(0,_dfa.Start); }
        }

        public bool IsFinal(State state)
        {
            return state == null || (state.Index == _s.Length && _dfa.Finals.Contains(state.Q));
        }

        #endregion
    }

    public class RegularExpressionMatcher : IRegularExpressionMatcher
    {
        private readonly Dfa _dfa;
        private readonly GreedySolver<RegularExpressionMatchingStateSpace.State, 
                                      RegularExpressionMatchingStateSpace.State, 
                                      RegularExpressionMatchingStateSpace.State> _greedySolver;

        public RegularExpressionMatcher(string expression)
        {
            _dfa =
                Dfa.BuildFromNfa(new ThompsonAutomatonBuilder().Build(new RegularExpressionParser().Parse(expression)));
            _greedySolver =
                new GreedySolver
                    <RegularExpressionMatchingStateSpace.State, RegularExpressionMatchingStateSpace.State,
                        RegularExpressionMatchingStateSpace.State>((space, d, f) => f);

        }

        public bool Match(string x)
        {
            return _greedySolver.Solve(new RegularExpressionMatchingStateSpace(_dfa, x)) != null;
        }

    }
}
